//
// press zM before doing ANYTHING or looking ANYWHERE, 
//  - if you're using VIM
//
// 
// Author:         If ( www.if-yu.info | if.html@gmail.com )
// Last edit date: Dec 31st, 2010
// Version:        unknown... Orz
// License:        GPL v3
//
// {{{ license
/*
 *                  Harmless: a harmless GoMoku AI
 *
 *  Copyright (C) 2010 If
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
// }}}


#include <utility>
#include <exception>
#include <stdexcept>
#include <algorithm>
#include <functional>
#include <iostream>
#include <cmath>
#include <time.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>

#ifdef DEBUG_GOMOKU
using std::cout;
using std::cerr;
using std::endl;
using std::flush;
#endif

#ifdef DEBUG_GOMOKU
#define dbg(...)   fprintf(stderr, __VA_ARGS__)
#define dexec(...) __VA_ARGS__
#else
#define dbg(...)   /* nothing at all */
#define dexec(...) /* nothing at all */
#endif

#ifdef DEBUG_GOMOKU
const clock_t    timeLimit=240*CLOCKS_PER_SEC/1000;
#else
const clock_t    timeLimit=830*CLOCKS_PER_SEC/1000;
#endif

#define MAX_VALUE  1000000
#define WIN_VALUE  900000
#define HTCAPACITY 2097152
#define X 'X'
#define O 'O'
// i am always O


// {{{ data structs
typedef uint32_t uint;
struct Pos {
    uint8_t row:4,
            col:4;
    inline Pos() { }
    inline Pos(uint8_t r, uint8_t c):
        row(r), col(c)
    { }
    inline Pos(uint32_t u):
        row((u>>4)&15), col(u&15)
    { }
    inline Pos(Pos const& p):
        row(p.row), col(p.col)
    { }
    inline uint8_t u8() const {
        return (row<<4)|col;
    }
    inline Pos&operator=(Pos const& p){
        *reinterpret_cast<uint8_t*>(this)=*reinterpret_cast<uint8_t const*>(&p);
        return *this;
    }
    inline bool operator==(Pos const& p) const {
        return this->row==p.row && this->col==p.col;
    }
};
std::ostream& operator<<(std::ostream& os, Pos const&p) {
    return os<<"("<<(int)p.row<<", "<<(int)p.col<<")";
}
struct Threat {
    Pos      p;   // position
    uint16_t lvl; // level ( same as it difined in maskTable )
};
inline bool operator<(Threat const& a, Threat const& b) {
    return a.lvl>b.lvl; // to make sort easier
}
struct HashKey {
    uint64_t k64;
    uint16_t type; // 0:exact; 1:alpha; 2:beta; 3:unknown;
    uint16_t depth;
    int32_t  v;
};
// }}}
// {{{ the game board
namespace board {
    typedef uint16_t BoardT[16];
    typedef uint16_t RotBoardT[32];

    // bit board X
    //        |  rotated X      
    //        V      V
    BoardT    bX,   rbX;

    //     left-top X
    //         |  right-top X
    //         V      V
    RotBoardT ltbX, rtbX;

    // same as above
    BoardT    bO,   rbO;
    RotBoardT ltbO, rtbO;

    //    each direction -----+
    //      ( 0: summerize    |
    //        1: horizontal   |
    //        2: vertical     |
    //        3: \ diagnal    |
    //        4: / diagnal )  |
    //    side ----+          |
    //             |          |
    //             V          V
    uint16_t  mark[2][16][16][5];
    //                ^   ^
    //                |   |
    //                +---+--- coordinate
    // summerize:
    // mark[r][c][1] | mark[r][c][2] | ...

    // goodMoves[depth][threatLevel] records good moves
    // threatLevel 3 : 4s / 4-3s like #OO-O, O#-OO &etc.
    // threatLevel 2 : 3s / 3-2s like -O-O#, #-O-O &etc.
    // threatLevel 1 : 2s / 2-1s like ---O#, -#-O- &etc.
    // threatLevel 0 : 1s        like ---#-, --#-- &etc.
    Threat    goodMoves[32][4][256];
    // size of above array
    int       gmSize[32][4];

    // all moves going to be checked in alphaBeta function
    // should be sorted after generate
    Threat    availableMoves[32][256];
    // size of above array
    int       amSize[32];

    // positions ---------------+
    //                          |
    // level     -----------+   |
    // [0] : 6 || 7         |   |
    // [1] : 8              |   |
    //                      |   |
    // depth     -------+   |   |
    //                  |   |   |
    //                  V   V   V
    uint8_t   tssStack[256][2][256];
    uint8_t   tssSize [256][2];

    // statistical info
    // statistic[0]: myself
    // statistic[1]: enimy
    int       statistic[2][32][8];

    // zobrist hash
    uint64_t  hash;
    uint8_t   win;
    // not used so far
    uint16_t  nThreats;
    uint16_t  ply;
    // not used at contest
    Pos       winLine[5];
    uint8_t   vfo,vfx,vto,vtx;
    Pos       steps[256];
    int8_t    i8Steps[256][2]; // for opening-book searching
    bool      obNotFound;      // current moves is not in opening book
    int       obIndex;         // index of current move in opening book - if exist
    int       iFirst;          // i am black

    clock_t   startTime;
    clock_t   endTime;

    // for debug:
#ifdef DEBUG_GOMOKU
    int       nodesSearched; 
    int       tssNodeSearched;
#endif
}
// }}}
// {{{ hash
static HashKey  hashTable[HTCAPACITY+3]={{0}};
static uint64_t zobristKeys[2][256]={{0},{0}};

inline uint64_t hash(uint64_t h, char who, Pos p) {
    return h^zobristKeys[who==O?0:1][(p.row<<4)|p.col];
}
inline void htupdate(uint64_t k64, int16_t type, int16_t depth, int32_t v) {
    uint32_t k32=((uint32_t)(k64^(k64>>32)))&(HTCAPACITY-1);
    HashKey *key=hashTable+k32;
    if(key->depth > depth) return;
    key->k64=k64;
    key->type=type;
    key->depth=depth;
    key->v=v;
}
inline HashKey const* htget(uint64_t k64) {
    uint32_t k32=((uint32_t)((k64>>32)^k64))&(HTCAPACITY-1);
    HashKey*pos=hashTable+k32;
    if(pos->k64==k64) return pos;
    return 0;
}
// }}}
// {{{ cached threats
// cachedThreats:
// cached every combination of nine pieces, for example -XOOO-O-X
//                                                          ^
//                                                          |
//                                                          +-------+
//                                                                  |
// what stores in the 32-bit data field is about the center piece  -+
// 
// 0001 010 0000 0 0000 0000 0 1000
// |    |   |      |    |      |
// |    |   |      |    +------+-------> places of threats of level 4 ( OOO#O )
// |    |   +------+-------------------> places of threats of level 3 ( OOO## )
// |    +-----------------> threat level ( 0 for not a threat, 1 for 3s, 2 for 4s, 4 for win )
// +----------------------> number of threats
uint32_t cachedThreats[512][512]={{0}};
// }}}
// {{{ constants
// {{{ bit operation
static const int bitsInChar[256]={
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,
2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,
4,5,5,6,5,6,6,7,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,
3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
};
static const int highestBit[256]={
0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
};
static const int lowestBit[256]={
8,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,
3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,
3,0,1,0,2,0,1,0,7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,0,1,0,2,0,1,0,
3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0
};
// }}}
// {{{ threat level
// 0 : occupied || no value at all
// 1 : 1        || broken 2      eg.    O---#  ||  O--#
// 2 : 2        || broken 2      eg.    O-#    ||  O#     ||  X-OO#-X
// 3 : broken 3 || blocked 3     eg.    OO--#  ||  O#--O  ||  #O--O
// 4 : broken 3                  eg.    OO-#   ||  O#-O   ||  #O-O
// 5 : open 3                    eg.    OO#    ||  O#O
// 6 : 4                         eg.    OOO-#  ||  OO-#O  ||  XOO#O- &etc.
// 7 : open 4                    ie.    -OOO#-
// 8 : 5                         ie.    OOOO# &etc.
static const uint8_t maskTable[4][32][6] = {
{
//  safe shift amount (TODO)
//         |    
//         V    
{0,0,0,0,0,1}, // 0  -----
{1,1,2,2,0,1}, // 1  ----O
{1,2,2,0,2,1}, // 2  ---O-
{3,4,5,0,0,1}, // 3  ---OO
{2,2,0,2,2,1}, // 4  --O--
{2,4,0,5,0,1}, // 5  --O-O
{3,4,0,0,4,1}, // 6  --OO-
{6,7,0,0,0,1}, // 7  --OOO
{2,0,2,2,1,1}, // 8  -O---
{3,0,4,4,0,1}, // 9  -O--O
{4,0,5,0,4,1}, // 10 -O-O-
{6,0,7,0,0,1}, // 11 -O-OO
{5,0,0,5,4,1}, // 12 -OO--
{6,0,0,7,0,1}, // 13 -OO-O
{7,0,0,0,7,1}, // 14 -OOO-
{8,0,0,0,0,1}, // 15 -OOOO
{0,2,2,1,1,1}, // 16 O----
{0,3,3,3,0,1}, // 17 O---O
{0,4,4,0,3,1}, // 18 O--O-
{0,6,6,0,0,1}, // 19 O--OO
{0,5,0,4,3,1}, // 20 O-O--
{0,6,0,6,0,1}, // 21 O-O-O
{0,7,0,0,6,1}, // 22 O-OO-
{0,8,0,0,0,1}, // 23 O-OOO
{0,0,5,4,3,1}, // 24 OO---
{0,0,6,6,0,1}, // 25 OO--O
{0,0,7,0,6,1}, // 26 OO-O-
{0,0,8,0,0,1}, // 27 OO-OO
{0,0,0,7,6,1}, // 28 OOO--
{0,0,0,8,0,1}, // 29 OOO-O
{0,0,0,0,8,1}, // 30 OOOO-
{0,0,0,0,0,4}  // 31 OOOOO
},
{
{0,0,0,0,0,1}, // 0  x-----
{0,1,2,2,0,1}, // 1  x----O
{1,2,2,0,2,1}, // 2  x---O-
{3,4,5,0,0,1}, // 3  x---OO
{1,2,0,2,2,1}, // 4  x--O--
{1,4,0,5,0,1}, // 5  x--O-O
{3,5,0,0,5,1}, // 6  x--OO-
{6,7,0,0,0,1}, // 7  x--OOO
{1,0,2,2,1,1}, // 8  x-O---
{1,0,4,4,0,1}, // 9  x-O--O
{3,0,5,0,4,1}, // 10 x-O-O-
{6,0,7,0,0,1}, // 11 x-O-OO
{3,0,0,5,4,1}, // 12 x-OO--
{6,0,0,7,0,1}, // 13 x-OO-O
{6,0,0,0,7,1}, // 14 x-OOO-
{8,0,0,0,0,1}, // 15 x-OOOO
{0,1,1,1,0,1}, // 16 xO----
{0,3,3,3,0,1}, // 17 xO---O
{0,3,3,0,3,1}, // 18 xO--O-
{0,6,6,0,0,1}, // 19 xO--OO
{0,3,0,3,3,1}, // 20 xO-O--
{0,6,0,6,0,1}, // 21 xO-O-O
{0,6,0,0,6,1}, // 22 xO-OO-
{0,8,0,0,0,1}, // 23 xO-OOO
{0,0,3,3,3,1}, // 24 xOO---
{0,0,6,6,0,1}, // 25 xOO--O
{0,0,6,0,6,1}, // 26 xOO-O-
{0,0,8,0,0,1}, // 27 xOO-OO
{0,0,0,6,6,1}, // 28 xOOO--
{0,0,0,8,0,1}, // 29 xOOO-O
{0,0,0,0,8,1}, // 30 xOOOO-
{0,0,0,0,0,3}  // 31 xOOOOO
},
{
{0,0,0,0,0,1}, // 0  -----x
{0,1,1,1,0,1}, // 1  ----Ox
{1,2,2,0,1,1}, // 2  ---O-x
{3,3,3,0,0,1}, // 3  ---OOx
{2,2,0,2,1,1}, // 4  --O--x
{3,3,0,3,0,1}, // 5  --O-Ox
{4,4,0,0,3,1}, // 6  --OO-x
{6,6,0,0,0,1}, // 7  --OOOx
{2,0,2,2,1,1}, // 8  -O---x
{3,0,3,3,0,1}, // 9  -O--Ox
{4,0,5,0,3,1}, // 10 -O-O-x
{6,0,6,0,0,1}, // 11 -O-OOx
{5,0,0,5,3,1}, // 12 -OO--x
{6,0,0,6,0,1}, // 13 -OO-Ox
{7,0,0,0,6,1}, // 14 -OOO-x
{8,0,0,0,0,1}, // 15 -OOOOx
{0,2,2,1,0,1}, // 16 O----x
{0,3,3,3,0,1}, // 17 O---Ox
{0,4,4,0,3,1}, // 18 O--O-x
{0,6,6,0,0,1}, // 19 O--OOx
{0,5,0,4,3,1}, // 20 O-O--x
{0,6,0,6,0,1}, // 21 O-O-Ox
{0,7,0,0,6,1}, // 22 O-OO-x
{0,8,0,0,0,1}, // 23 O-OOOx
{0,0,5,4,3,1}, // 24 OO---x
{0,0,6,6,0,1}, // 25 OO--Ox
{0,0,7,0,6,1}, // 26 OO-O-x
{0,0,8,0,0,1}, // 27 OO-OOx
{0,0,0,7,6,1}, // 28 OOO--x
{0,0,0,8,0,1}, // 29 OOO-Ox
{0,0,0,0,8,1}, // 30 OOOO-x
{0,0,0,0,0,3}  // 31 OOOOOx
},
{
{0,0,0,0,0,5}, // 0  x-----x
{0,1,1,1,0,5}, // 1  x----Ox
{0,1,1,0,0,5}, // 2  x---O-x
{3,3,3,0,0,5}, // 3  x---OOx
{1,1,0,1,1,5}, // 4  x--O--x
{3,3,0,3,0,5}, // 5  x--O-Ox
{3,3,0,0,3,5}, // 6  x--OO-x
{6,6,0,0,0,5}, // 7  x--OOOx
{1,0,1,1,0,5}, // 8  x-O---x
{3,0,3,3,0,5}, // 9  x-O--Ox
{3,0,3,0,3,5}, // 10 x-O-O-x
{6,0,6,0,0,5}, // 11 x-O-OOx
{3,0,0,3,3,5}, // 12 x-OO--x
{6,0,0,6,0,5}, // 13 x-OO-Ox
{6,0,0,0,6,5}, // 14 x-OOO-x
{8,0,0,0,0,5}, // 15 x-OOOOx
{0,2,1,1,1,5}, // 16 xO----x
{0,2,2,2,0,5}, // 17 xO---Ox
{0,3,3,0,3,5}, // 18 xO--O-x
{0,6,6,0,0,5}, // 19 xO--OOx
{0,3,0,3,3,5}, // 20 xO-O--x
{0,6,0,6,0,5}, // 21 xO-O-Ox
{0,6,0,0,6,5}, // 22 xO-OO-x
{0,8,0,0,0,5}, // 23 xO-OOOx
{0,0,3,3,3,5}, // 24 xOO---x
{0,0,6,6,0,5}, // 25 xOO--Ox
{0,0,6,0,6,5}, // 26 xOO-O-x
{0,0,8,0,0,5}, // 27 xOO-OOx
{0,0,0,6,6,5}, // 28 xOOO--x
{0,0,0,8,0,5}, // 29 xOOO-Ox
{0,0,0,0,8,5}, // 30 xOOOO-x
{0,0,0,0,0,5}  // 31 xOOOOOx
}
};
// }}}
// {{{ power
static const int
SM_10=2,
SM_11=137,
SM_20=5,
SM_21=526,
SM_22=2464,
SM_30=778,
SM_31=1104,
SM_32=5408,
SM_33=459,
SM_43=2,
SM_44=4,
SM_4x=3,
SO_10=8,
SO_11=2,
SO_20=18,
SO_21=14,
SO_22=2802,
SO_30=1424,
SO_31=811,
SO_32=708,
SO_33=3522,
SO_43=213,
SO_44=1546,
SO_4x=11873;
// }}}
// {{{ opening book
//             position -----------------+
//             index    -----------+     |
//             who wins --------+  |     |
//             ( 0: black;      |  |     |
//               1: white. )    V  V     V
static int8_t openingBook[2][8*1024][64][2] = {
// black win
{
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{6,9},{8,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,8},{9,7},{9,6},{8,6},{9,5},{10,8},{7,5},{11,9},{12,10},{11,7},{10,7},{11,8},{11,10},{12,8},{13,8},{12,6},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,8},{9,7},{9,6},{8,6},{9,5},{10,8},{7,5},{11,9},{12,10},{11,7},{10,7},{11,8},{11,6},{11,10},{11,11},{9,8},{10,9},{12,8},{13,8},{9,9},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,8},{9,7},{9,6},{8,6},{9,5},{10,8},{11,9},{7,5},{6,4},{7,6},{7,4},{10,7},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,8},{9,7},{8,6},{9,6},{10,5},{10,7},{11,7},{9,8},{9,9},{7,6},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,8},{9,7},{8,6},{9,6},{10,5},{10,7},{11,7},{9,8},{9,5},{10,9},{7,6},{11,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,8},{9,7},{8,6},{9,6},{10,5},{10,7},{11,7},{9,8},{9,5},{10,9},{11,10},{11,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,8},{9,7},{8,6},{9,6},{6,9},{10,7},{11,7},{10,5},{11,4},{9,5},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,8},{9,7},{7,6},{8,6},{9,5},{10,7},{11,7},{10,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,8},{9,7},{6,9},{8,6},{9,5},{7,5},{10,8},{6,4},{5,3},{7,4},{7,6},{8,4},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,8},{9,7},{6,9},{8,6},{9,5},{7,5},{6,4},{7,6},{7,4},{9,6},{10,6},{9,8},{10,9},{10,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,6},{9,6},{10,5},{9,8},{8,8},{9,7},{9,9},{10,7},{11,7},{7,6},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,6},{9,6},{10,5},{9,8},{8,8},{9,7},{9,5},{10,7},{11,7},{10,9},{7,6},{11,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,6},{9,6},{10,5},{9,8},{8,8},{9,7},{9,5},{10,7},{11,7},{10,9},{11,10},{11,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,6},{9,6},{10,5},{9,8},{10,8},{8,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,6},{9,6},{6,9},{9,8},{8,8},{7,6},{6,5},{9,7},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{8,6},{9,6},{6,9},{9,8},{8,8},{7,6},{10,9},{10,5},{11,4},{6,5},{5,4},{7,5},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{7,6},{8,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{6,6},{8,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{4,7},{8,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{4,8},{8,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{4,9},{8,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{7,9},{8,7},{6,10},{8,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{6,9},{8,8},{9,8},{8,6},{9,5},{7,9},{7,10},{9,7},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{6,9},{8,8},{9,8},{8,6},{9,5},{7,9},{7,6},{7,11},{7,10},{4,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{6,9},{8,8},{5,8},{8,6},{9,5},{7,6},{7,5},{8,7},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{6,9},{8,8},{5,8},{8,6},{9,5},{7,6},{7,9},{7,5},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{8,6},{8,8},{5,8},{9,8},{10,8},{9,9},{6,6},{7,9},{7,6},{8,9},{6,9},{7,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{8,6},{8,8},{5,8},{9,8},{10,8},{9,9},{6,6},{7,9},{7,10},{9,7},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{8,6},{8,8},{5,8},{9,8},{10,8},{9,9},{10,10},{7,9},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{8,6},{8,8},{9,8},{7,9},{7,10},{6,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{8,6},{8,8},{9,8},{7,9},{7,6},{7,11},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{8,7},{8,8},{9,8},{7,9},{7,10},{6,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{8,7},{8,8},{9,8},{7,9},{7,6},{7,11},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{8,8},{7,9},{7,6},{7,11},{7,10},{6,10},{4,8},{6,9},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{8,8},{7,9},{7,6},{7,11},{7,10},{6,10},{8,12},{6,9},{8,9},{6,11},{6,12},{4,8},{3,7},{4,9},{3,9},{3,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{8,8},{7,9},{7,10},{6,9},{4,9},{7,6},{7,5},{8,6},{9,5},{9,6},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{8,8},{7,9},{7,10},{6,9},{8,9},{7,6},{7,5},{8,6},{9,5},{9,6},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{4,8},{8,8},{9,8},{7,9},{7,10},{8,6},{9,5},{9,7},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{4,8},{8,8},{9,8},{7,9},{7,6},{6,9},{4,9},{8,9},{9,9},{8,6},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{4,8},{8,8},{9,8},{7,9},{7,6},{6,9},{8,9},{8,6},{9,5},{9,7},{6,10},{8,7},{9,6},{7,10},{7,11},{10,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{4,8},{8,8},{9,8},{7,9},{7,6},{6,9},{8,9},{8,6},{9,5},{9,7},{10,6},{5,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{4,8},{8,8},{9,8},{7,9},{7,10},{8,6},{9,5},{9,7},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{4,10},{7,8},{4,8},{8,8},{5,8},{8,6},{9,5},{10,8},{9,8},{7,5},{15,15}},

{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,8},{3,9},{2,9},{5,11},{6,12},{5,10},{5,12},{6,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,8},{3,9},{2,9},{5,11},{6,12},{5,10},{5,8},{6,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,8},{3,9},{2,9},{5,11},{2,8},{5,10},{5,12},{6,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,8},{3,9},{2,9},{5,11},{2,8},{5,10},{5,8},{6,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,8},{3,9},{6,9},{2,8},{1,7},{5,11},{6,12},{5,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,8},{3,9},{6,9},{2,8},{5,11},{1,9},{2,9},{3,7},{4,6},{1,7},{0,6},{1,6},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,8},{3,9},{6,9},{2,8},{5,11},{1,9},{2,9},{3,7},{0,10},{3,8},{3,6},{5,10},{6,11},{1,7},{0,6},{1,6},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,8},{3,9},{6,9},{2,8},{5,11},{1,9},{2,9},{3,7},{0,10},{3,8},{3,6},{5,10},{2,7},{3,10},{2,10},{6,11},{7,12},{7,10},{6,10},{5,12},{4,13},{7,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,8},{3,9},{6,9},{2,8},{5,11},{1,9},{2,9},{3,7},{0,10},{3,8},{3,6},{5,10},{2,7},{3,10},{2,10},{6,11},{7,12},{7,10},{6,10},{5,12},{8,9},{2,11},{1,12},{4,13},{3,14},{1,7},{0,6},{1,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,8},{3,9},{6,9},{2,8},{5,11},{1,9},{2,9},{3,7},{0,10},{3,8},{3,6},{5,10},{2,7},{3,10},{6,10},{1,7},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,8},{3,9},{6,9},{2,8},{5,11},{1,9},{2,9},{3,7},{0,10},{3,8},{3,10},{3,6},{3,5},{4,6},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,7},{3,7},{6,10},{7,8},{5,8},{7,9},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,7},{3,7},{6,10},{7,8},{8,8},{3,8},{5,8},{5,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,7},{3,7},{6,10},{7,8},{3,8},{8,8},{5,8},{7,9},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,7},{3,7},{2,6},{5,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,11},{3,8},{5,8},{2,7},{5,10},{2,6},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,11},{3,8},{5,8},{2,7},{1,6},{3,7},{6,10},{4,7},{4,6},{2,6},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,11},{3,8},{5,8},{2,7},{1,6},{3,7},{2,6},{4,6},{4,7},{5,5},{2,8},{6,4},{7,3},{6,6},{4,4},{6,10},{7,11},{6,11},{5,10},{6,9},{6,12},{7,9},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,11},{3,8},{5,8},{2,7},{1,6},{3,7},{2,6},{4,6},{4,7},{5,5},{2,8},{6,4},{7,3},{6,6},{8,8},{4,4},{3,3},{3,4},{5,4},{3,6},{3,5},{6,10},{7,11},{6,11},{5,10},{6,9},{6,12},{7,9},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,11},{3,8},{5,8},{2,7},{1,6},{3,7},{2,6},{4,6},{4,7},{5,5},{6,4},{8,8},{6,6},{6,10},{7,11},{6,11},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,11},{3,8},{5,8},{2,7},{1,6},{3,7},{2,6},{4,6},{4,7},{5,5},{6,4},{8,8},{9,9},{6,10},{7,11},{6,11},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,11},{3,8},{5,8},{2,7},{1,6},{3,7},{2,6},{4,6},{4,7},{5,5},{6,4},{8,8},{4,4},{6,10},{7,11},{6,11},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,11},{3,8},{7,8},{5,8},{2,8},{4,7},{4,6},{6,9},{7,10},{6,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{3,9},{4,8},{4,11},{3,8},{7,8},{5,8},{2,8},{4,7},{4,6},{6,9},{3,6},{5,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{5,11},{3,10},{6,10},{2,10},{1,10},{2,11},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{5,11},{3,10},{2,10},{4,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{3,9},{3,10},{2,10},{4,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{3,9},{3,10},{6,10},{2,11},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{4,8},{5,12},{5,11},{6,11},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{4,8},{5,12},{5,10},{6,11},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{4,8},{5,12},{5,8},{7,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{4,8},{5,12},{5,8},{7,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{6,10},{4,11},{4,12},{5,11},{5,12},{3,9},{6,12},{4,8},{4,7},{2,8},{1,7},{3,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{6,10},{4,11},{4,12},{5,11},{5,12},{3,9},{2,8},{3,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{6,10},{4,11},{4,12},{5,11},{5,8},{6,11},{7,12},{3,9},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{6,10},{4,11},{4,12},{5,11},{5,8},{6,11},{3,8},{7,12},{8,13},{6,12},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{6,10},{4,11},{4,8},{6,11},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{4,11},{5,11},{5,12},{3,9},{6,12},{3,8},{6,11},{2,8},{1,7},{4,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{4,11},{5,11},{5,12},{3,9},{6,12},{3,8},{2,7},{2,8},{1,7},{4,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{4,11},{5,11},{5,12},{3,9},{2,8},{3,10},{2,10},{6,10},{7,10},{3,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{4,11},{5,11},{5,12},{3,9},{2,8},{3,10},{6,10},{3,8},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{4,11},{5,11},{5,8},{3,9},{6,12},{6,10},{3,10},{4,8},{7,11},{2,11},{1,7},{3,7},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{4,11},{5,11},{5,8},{3,9},{6,12},{6,10},{3,10},{4,8},{3,7},{7,11},{8,12},{7,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{4,11},{5,11},{5,8},{3,9},{6,12},{6,10},{7,10},{2,8},{1,7},{2,9},{1,9},{2,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{6,9},{5,10},{5,12},{6,10},{15,15}},
{{7,7},{6,7},{6,8},{5,7},{5,9},{8,6},{4,10},{3,11},{4,9},{4,11},{3,9},{16,16}},
{{7,7},{6,7},{6,8},{5,9},{8,6},{5,8},{7,6},{5,7},{5,6},{6,6},{7,5},{7,4},{9,5},{10,4},{9,7},{10,8},{9,6},{16,16}},
{{7,7},{6,7},{6,8},{5,9},{8,6},{7,6},{8,5},{8,7},{9,5},{10,4},{9,6},{7,4},{9,4},{16,16}},
{{7,7},{6,7},{6,8},{5,9},{8,6},{7,8},{7,6},{7,5},{9,6},{10,6},{9,8},{9,7},{8,7},{10,9},{8,5},{16,16}},
{{7,7},{6,7},{6,8},{5,9},{8,6},{7,8},{7,6},{7,5},{9,6},{10,6},{9,8},{9,7},{8,7},{6,5},{8,9},{16,16}},
{{7,7},{6,7},{6,8},{5,9},{8,6},{8,7},{9,5},{10,4},{7,6},{7,5},{6,6},{5,6},{8,8},{16,16}},
{{7,7},{6,7},{6,8},{5,9},{8,6},{6,9},{7,6},{7,8},{9,5},{10,4},{9,6},{16,16}},
{{7,7},{6,7},{6,8},{5,9},{8,6},{8,5},{7,6},{7,8},{9,5},{10,4},{9,6},{10,6},{9,7},{16,16}},
{{7,7},{6,7},{6,8},{7,8},{8,9},{6,9},{8,6},{5,9},{8,7},{8,8},{7,6},{9,8},{6,6},{16,16}},
{{7,7},{6,7},{6,8},{7,8},{8,9},{6,9},{8,6},{5,9},{8,7},{8,8},{7,6},{6,5},{10,6},{16,16}},
{{7,7},{6,7},{6,8},{7,8},{8,9},{6,9},{8,6},{5,9},{8,7},{8,8},{7,6},{4,9},{3,9},{5,10},{9,8},{16,16}},
{{7,7},{6,7},{6,8},{7,8},{8,9},{6,9},{8,6},{5,9},{8,7},{8,8},{7,6},{4,9},{3,9},{5,9},{9,8},{16,16}},
{{7,7},{6,7},{6,8},{7,8},{8,9},{6,9},{8,6},{9,5},{8,7},{8,8},{9,8},{10,7},{10,9},{11,10},{9,9},{11,9},{10,6},{7,6},{9,11},{9,10},{8,10},{7,9},{7,11},{16,16}},
{{7,7},{6,7},{6,8},{7,8},{8,9},{6,9},{8,6},{9,5},{8,7},{8,8},{9,8},{9,7},{10,7},{7,10},{10,9},{7,6},{11,6},{12,5},{11,10},{12,11},{11,9},{9,9},{11,8},{11,7},{10,8},{15,15}},
{{7,7},{6,7},{6,8},{7,8},{8,9},{8,8},{5,9},{8,6},{6,9},{16,16}},
{{7,7},{6,7},{6,8},{7,8},{8,9},{5,6},{8,6},{5,9},{8,8},{8,7},{9,9},{6,6},{10,10},{11,11},{10,9},{11,9},{10,8},{15,15}},
{{7,7},{6,7},{6,8},{7,8},{8,9},{5,6},{8,6},{9,5},{8,8},{8,7},{9,9},{10,10},{11,9},{10,9},{10,8},{9,7},{8,10},{15,15}},
{{7,7},{6,7},{6,8},{7,8},{8,9},{7,10},{8,6},{5,9},{8,8},{8,7},{9,6},{9,5},{9,9},{15,15}},
{{7,7},{6,7},{6,8},{7,8},{8,9},{7,10},{8,6},{9,5},{9,9},{8,8},{5,9},{4,10},{7,9},{6,9},{8,10},{15,15}},
{{7,7},{6,7},{6,8},{5,6},{7,8},{5,8},{7,6},{7,9},{5,5},{6,6},{7,5},{7,4},{6,5},{8,5},{8,6},{5,9},{8,7},{9,8},{6,4},{5,3},{9,6},{15,15}},
{{7,7},{6,7},{6,8},{5,6},{7,8},{5,8},{7,6},{7,9},{5,5},{6,6},{7,5},{7,4},{6,5},{8,5},{8,6},{5,9},{8,7},{9,8},{6,4},{10,8},{9,6},{15,15}},
{{7,7},{6,7},{6,8},{5,6},{7,8},{5,8},{7,6},{7,9},{5,5},{7,5},{8,8},{6,6},{8,7},{15,15}},
{{7,7},{6,7},{6,8},{5,6},{7,8},{5,8},{7,6},{7,5},{5,9},{8,6},{4,9},{7,9},{4,10},{3,11},{4,8},{4,7},{4,11},{4,12},{6,9},{5,10},{6,10},{15,15}},
{{7,7},{6,7},{6,8},{5,6},{7,8},{5,9},{7,9},{7,10},{5,7},{8,10},{8,8},{15,15}},
{{7,7},{6,7},{6,8},{5,6},{7,8},{5,9},{7,9},{7,6},{5,8},{4,8},{8,8},{9,8},{8,10},{15,15}},
{{7,7},{6,7},{6,8},{5,6},{7,8},{4,7},{8,8},{5,8},{9,8},{10,8},{9,9},{15,15}},
{{7,7},{6,7},{6,8},{5,6},{7,8},{4,7},{8,8},{9,8},{7,9},{7,6},{5,9},{8,6},{4,10},{3,11},{4,8},{15,15}},
{{7,7},{6,7},{6,8},{4,7},{7,8},{5,9},{8,8},{9,8},{7,9},{7,10},{9,7},{10,6},{9,9},{6,6},{8,9},{10,9},{8,10},{15,15}},
{{7,7},{6,7},{6,8},{8,6},{5,9},{5,8},{4,9},{4,10},{7,9},{6,9},{7,10},{7,8},{8,10},{9,11},{9,10},{10,10},{5,10},{6,10},{6,11},{7,12},{5,12},{8,9},{2,7},{3,8},{4,11},{5,11},{2,9},{3,10},{2,8},{2,10},{2,6},{2,5},{4,6},{5,7},{1,9},{15,15}},
{{7,7},{6,7},{6,8},{8,6},{5,9},{6,9},{4,10},{3,11},{5,8},{4,8},{5,7},{5,6},{7,9},{8,10},{7,8},{7,10},{8,8},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{8,10},{6,7},{7,8},{8,7},{9,7},{8,5},{8,6},{7,6},{5,8},{9,8},{10,9},{10,7},{7,10},{7,4},{9,6},{6,5},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{8,10},{6,7},{7,8},{8,7},{9,7},{8,5},{8,6},{7,6},{5,8},{9,8},{6,5},{10,7},{11,6},{10,9},{11,10},{9,9},{7,9},{10,10},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{8,10},{6,7},{7,8},{8,7},{5,7},{7,9},{9,7},{10,9},{9,9},{7,6},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{8,10},{6,7},{7,8},{8,7},{5,7},{7,9},{9,7},{10,9},{6,9},{7,6},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{8,10},{6,7},{8,7},{7,8},{5,6},{7,9},{7,6},{8,6},{4,6},{3,6},{9,8},{7,11},{7,10},{9,10},{10,11},{10,9},{6,5},{5,4},{9,9},{8,11},{7,12},{5,11},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{7,6},{6,9},{8,6},{5,6},{8,7},{9,8},{6,5},{10,7},{7,10},{10,8},{6,4},{6,7},{9,6},{10,6},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{7,6},{6,9},{8,6},{5,6},{8,10},{5,7},{10,6},{9,6},{7,9},{8,7},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{7,6},{6,9},{8,6},{5,6},{8,10},{5,7},{10,6},{9,6},{8,7},{5,8},{5,9},{4,7},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{7,6},{6,9},{8,6},{5,6},{7,9},{8,10},{8,11},{9,10},{7,10},{9,9},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{8,6},{7,9},{7,6},{9,6},{6,9},{6,7},{9,7},{7,10},{5,6},{4,6},{10,8},{7,11},{7,8},{11,9},{7,5},{6,4},{9,9},{6,11},{5,12},{8,10},{8,11},{7,12},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{8,6},{7,9},{6,9},{6,10},{9,7},{8,10},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{8,7},{7,9},{6,5},{6,9},{5,9},{9,9},{10,9},{10,10},{11,11},{6,10},{5,11},{9,8},{6,4},{6,7},{6,3},{6,2},{9,7},{7,8},{7,10},{9,10},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{7,9},{8,10},{8,7},{7,10},{6,9},{6,10},{5,10},{7,8},{6,5},{6,7},{9,10},{9,8},{6,11},{10,8},{11,8},{9,9},{11,7},{7,11},{6,12},{10,10},{11,11},{8,12},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{7,9},{8,10},{8,7},{7,10},{6,9},{6,10},{5,10},{7,8},{6,5},{6,7},{9,10},{9,8},{6,11},{10,8},{11,8},{9,9},{7,11},{10,7},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{7,8},{8,10},{8,7},{6,9},{9,9},{8,11},{8,12},{7,10},{5,8},{9,10},{4,8},{3,8},{6,10},{10,9},{11,8},{10,10},{11,10},{10,13},{9,12},{10,11},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{6,7},{6,9},{9,9},{8,7},{8,10},{8,5},{8,6},{9,6},{7,8},{10,7},{11,8},{9,8},{11,6},{6,5},{9,7},{7,4},{6,3},{7,6},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{6,7},{6,9},{9,9},{8,7},{8,10},{8,5},{8,6},{9,6},{7,8},{10,7},{11,8},{9,8},{11,6},{6,5},{7,6},{9,7},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{5,7},{4,9},{7,5},{4,8},{6,5},{6,9},{6,4},{6,7},{8,4},{9,3},{6,3},{6,2},{9,9},{7,8},{15,15}},
{{7,7},{6,8},{8,8},{6,6},{8,9},{5,7},{4,9},{7,5},{4,8},{6,9},{6,7},{8,4},{9,3},{7,8},{8,7},{15,15}},
{{7,7},{6,8},{8,8},{9,9},{6,6},{7,6},{5,5},{4,4},{7,5},{4,6},{9,7},{4,5},{4,7},{4,3},{4,2},{5,7},{7,9},{6,10},{8,7},{15,15}},
{{7,7},{6,8},{8,8},{9,9},{6,6},{7,9},{5,7},{8,9},{5,5},{4,4},{6,9},{5,6},{7,5},{4,8},{6,5},{8,5},{6,7},{15,15}},
{{7,7},{6,8},{8,8},{8,9},{6,6},{9,9},{5,7},{7,5},{5,5},{4,4},{5,6},{5,4},{6,7},{4,7},{7,6},{15,15}},

{{7,7},{5,7},{9,7},{16,16}},
{{7,7},{5,8},{6,6},{5,5},{5,7},{16,16}},
{{7,7},{5,9},{8,8},{6,6},{8,7},{16,16}}
},
// white win
{
{{7,7},{6,6},{5,5},{6,7},{15,15}},
{{7,7},{6,6},{6,7},{5,7},{7,5},{6,8},{16,16}},
{{7,7},{6,6},{7,9},{7,8},{16,16}},
{{7,7},{6,6},{5,7},{4,7},{16,16}},
{{7,7},{6,6},{5,6},{6,7},{16,16}},
{{7,7},{6,6},{7,8},{7,6},{7,9},{5,7},{7,5},{5,4},{16,16}}
}
};
int obSize[2] = {
    144,
    6
};
// }}}
// {{{ affine
static const uint8_t affineLT[32][16] = {
{255, 255, 255, 255, 255, 255, 255,  14, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255,  13,  30, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255,  12,  29,  46, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255,  11,  28,  45,  62, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255,  10,  27,  44,  61,  78, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255,   9,  26,  43,  60,  77,  94, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255,   8,  25,  42,  59,  76,  93, 110, 255, 255, 255, 255, 255},
{255, 255, 255,   7,  24,  41,  58,  75,  92, 109, 126, 255, 255, 255, 255, 255},
{255, 255, 255,   6,  23,  40,  57,  74,  91, 108, 125, 142, 255, 255, 255, 255},
{255, 255,   5,  22,  39,  56,  73,  90, 107, 124, 141, 158, 255, 255, 255, 255},
{255, 255,   4,  21,  38,  55,  72,  89, 106, 123, 140, 157, 174, 255, 255, 255},
{255,   3,  20,  37,  54,  71,  88, 105, 122, 139, 156, 173, 190, 255, 255, 255},
{255,   2,  19,  36,  53,  70,  87, 104, 121, 138, 155, 172, 189, 206, 255, 255},
{  1,  18,  35,  52,  69,  86, 103, 120, 137, 154, 171, 188, 205, 222, 255, 255},
{  0,  17,  34,  51,  68,  85, 102, 119, 136, 153, 170, 187, 204, 221, 238, 255},
{ 16,  33,  50,  67,  84, 101, 118, 135, 152, 169, 186, 203, 220, 237, 255, 255},
{255,  32,  49,  66,  83, 100, 117, 134, 151, 168, 185, 202, 219, 236, 255, 255},
{255,  48,  65,  82,  99, 116, 133, 150, 167, 184, 201, 218, 235, 255, 255, 255},
{255, 255,  64,  81,  98, 115, 132, 149, 166, 183, 200, 217, 234, 255, 255, 255},
{255, 255,  80,  97, 114, 131, 148, 165, 182, 199, 216, 233, 255, 255, 255, 255},
{255, 255, 255,  96, 113, 130, 147, 164, 181, 198, 215, 232, 255, 255, 255, 255},
{255, 255, 255, 112, 129, 146, 163, 180, 197, 214, 231, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 128, 145, 162, 179, 196, 213, 230, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 144, 161, 178, 195, 212, 229, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 160, 177, 194, 211, 228, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 176, 193, 210, 227, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 192, 209, 226, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 208, 225, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 224, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
};
static const uint8_t affineRT[32][16] = {
{255, 255, 255, 255, 255, 255, 255,   0, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255,   1,  16, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255,   2,  17,  32, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255,   3,  18,  33,  48, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255,   4,  19,  34,  49,  64, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255,   5,  20,  35,  50,  65,  80, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255,   6,  21,  36,  51,  66,  81,  96, 255, 255, 255, 255, 255},
{255, 255, 255,   7,  22,  37,  52,  67,  82,  97, 112, 255, 255, 255, 255, 255},
{255, 255, 255,   8,  23,  38,  53,  68,  83,  98, 113, 128, 255, 255, 255, 255},
{255, 255,   9,  24,  39,  54,  69,  84,  99, 114, 129, 144, 255, 255, 255, 255},
{255, 255,  10,  25,  40,  55,  70,  85, 100, 115, 130, 145, 160, 255, 255, 255},
{255,  11,  26,  41,  56,  71,  86, 101, 116, 131, 146, 161, 176, 255, 255, 255},
{255,  12,  27,  42,  57,  72,  87, 102, 117, 132, 147, 162, 177, 192, 255, 255},
{ 13,  28,  43,  58,  73,  88, 103, 118, 133, 148, 163, 178, 193, 208, 255, 255},
{ 14,  29,  44,  59,  74,  89, 104, 119, 134, 149, 164, 179, 194, 209, 224, 255},
{ 30,  45,  60,  75,  90, 105, 120, 135, 150, 165, 180, 195, 210, 225, 255, 255},
{255,  46,  61,  76,  91, 106, 121, 136, 151, 166, 181, 196, 211, 226, 255, 255},
{255,  62,  77,  92, 107, 122, 137, 152, 167, 182, 197, 212, 227, 255, 255, 255},
{255, 255,  78,  93, 108, 123, 138, 153, 168, 183, 198, 213, 228, 255, 255, 255},
{255, 255,  94, 109, 124, 139, 154, 169, 184, 199, 214, 229, 255, 255, 255, 255},
{255, 255, 255, 110, 125, 140, 155, 170, 185, 200, 215, 230, 255, 255, 255, 255},
{255, 255, 255, 126, 141, 156, 171, 186, 201, 216, 231, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 142, 157, 172, 187, 202, 217, 232, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 158, 173, 188, 203, 218, 233, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 174, 189, 204, 219, 234, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 190, 205, 220, 235, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 206, 221, 236, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 222, 237, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 238, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255},
{255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255}
};
// }}}
// }}} constants
// {{{ init on startup's
class ZobristKeyInitizer {
public:
    ZobristKeyInitizer(){
        for(int i=0;i<2;++i) {
            for(int j=0;j<256;++j) {
                uint64_t 
                k64 =rand();
                k64^=(uint64_t)rand() << 15;
                k64^=(uint64_t)rand() << 30;
                k64^=(uint64_t)rand() << 45;
                k64^=(uint64_t)rand() << 60;
                zobristKeys[i][j]=k64;
            }
        }
    }
} zobristKeyInitizer;

class CachedThreatsInitizer {
public:
    CachedThreatsInitizer() {
        for(uint o=0;o<512;++o) {
            if(bitsInChar[o&255]+bitsInChar[(o>>8)&255]<=2)
                continue;
            for(uint x=0;x<512;++x) {
                if(x&o) // impossible
                    continue;
                uint c=0,lv=0,msk=0;
                for(int pos=0;pos<5;++pos) {
                    if ((x>>pos)&31) continue; // interrupted
                    uint tmp=(o>>pos)&31;
                    if (!tmp) continue;
                    int left=0,right=0;
                    if (pos==0) left=1;
                    else        left=x>>(pos-1)&1;
                    if (pos==4) right=1;
                    else        right=x>>(pos+5)&1;
                    uint8_t const*S=maskTable[(left<<1)|right][tmp&31]+4;
                    if(tmp==31) {
                        lv|=4;
                    } else {
                        for(int i=0;i<5;++i) {
                            uint8_t v=*S--;
                            if(v==8) {
                                lv|=2;
                                ++c;
                                msk|=1<<(pos+i);
                            } else if(v>=6) {
                                lv|=1;
                                ++c;
                                msk|=1<<(pos+i+9);
                            }
                        }
                    }
                }
                cachedThreats[o][x]=c<<21|lv<<18|msk;
            }
        }
    }
} cachedThreatsInitizer;

// }}}
// {{{ misc functions
inline int bitCount16(uint16_t n) {
    return bitsInChar[n&0xffu]+bitsInChar[(n>>8)&0xffu];
}
inline int bitCount32(uint32_t n) {
    return bitsInChar[n&0xffu]+bitsInChar[(n>>8)&0xffu]+bitsInChar[(n>>16)&0xffu]+bitsInChar[(n>>24)&0xffu];
}

inline char get(int row, int col) {
#ifdef DEBUG_GOMOKU
    if ((board::bX[row]>>col)&1 && (board::bO[row]>>col)&1)
        return '@';
#endif
    if ((board::bX[row]>>col)&1)
        return X;
    else if((board::bO[row]>>col)&1)
        return O;
    return 0;
}
inline char get(Pos p) {
    return get(p.row,p.col);
}
inline int getX(int row, int col) {
    return (board::bX[row]>>col)&1;
}
inline int getO(int row, int col) {
    return (board::bO[row]>>col)&1;
}

inline void set(int row, int col, char value) {
    Pos p(row,col);
#ifdef DEBUG_GOMOKU
    if(get(row,col)) {
        cerr<<"Error: set("<<row<<", "<<col<<", "<<value<<")\n";
    }
#endif
    switch(value) {
    case X:
        board::bX[row]  |= 1<<col;
        board::rbX[col] |= 1<<row;
        board::ltbX[row-col+14] |= 1<<((row+col)>>1);
        board::rtbX[row+col]    |= 1<<((row-col+14)>>1);
        break;
    case O:
        board::bO[row]  |= 1<<col;
        board::rbO[col] |= 1<<row;
        board::ltbO[row-col+14] |= 1<<((row+col)>>1);
        board::rtbO[row+col]    |= 1<<((row-col+14)>>1);
        break;
    }
    board::hash=hash(board::hash,value,p);
    board::steps[board::ply++]=Pos(row,col);
}

inline void setLite(Pos p, char value) {
    int row=p.row, col=p.col;
#ifdef DEBUG_GOMOKU
    if(get(row,col)) {
        cerr<<"Error: setLite("<<p<<", "<<value<<")\n";
    }
#endif
    switch(value) {
    case X:
        board::bX[row]  |= 1<<col;
        board::rbX[col] |= 1<<row;
        board::ltbX[row-col+14] |= 1<<((row+col)>>1);
        board::rtbX[row+col]    |= 1<<((row-col+14)>>1);
        break;
    case O:
        board::bO[row]  |= 1<<col;
        board::rbO[col] |= 1<<row;
        board::ltbO[row-col+14] |= 1<<((row+col)>>1);
        board::rtbO[row+col]    |= 1<<((row-col+14)>>1);
        break;
    }
}

inline void unset(int row, int col, char value) {
#ifdef DEBUG_GOMOKU
    if(!get(row,col)) {
        cerr<<"Error: unset("<<row<<", "<<col<<", "<<value<<")\n";
    }
#endif
    switch(value) {
    case X:
        board::bX[row]  &= ~(1<<col);
        board::rbX[col] &= ~(1<<row);
        board::ltbX[row-col+14] &= ~(1<<((row+col)>>1));
        board::rtbX[row+col]    &= ~(1<<((row-col+14)>>1));
        break;
    case O:
        board::bO[row]  &= ~(1<<col);
        board::rbO[col] &= ~(1<<row);
        board::ltbO[row-col+14] &= ~(1<<((row+col)>>1));
        board::rtbO[row+col]    &= ~(1<<((row-col+14)>>1));
        break;
    }
    board::hash=hash(board::hash,value,Pos(row,col));
    --board::ply;
}

inline void unsetLite(Pos p, char value) {
    int row=p.row,
        col=p.col;
#ifdef DEBUG_GOMOKU
    if(!get(row,col)) {
        cerr<<"Error: unsetlite("<<row<<", "<<col<<", "<<value<<")\n";
    }
#endif

    switch(value) {
    case X:
        board::bX[row]  &= ~(1<<col);
        board::rbX[col] &= ~(1<<row);
        board::ltbX[row-col+14] &= ~(1<<((row+col)>>1));
        board::rtbX[row+col]    &= ~(1<<((row-col+14)>>1));
        break;
    case O:
        board::bO[row]  &= ~(1<<col);
        board::rbO[col] &= ~(1<<row);
        board::ltbO[row-col+14] &= ~(1<<((row+col)>>1));
        board::rtbO[row+col]    &= ~(1<<((row-col+14)>>1));
        break;
    }
}

#ifdef DEBUG_GOMOKU
void print(Pos hl) {
    int r,c;
    cout<<"   0 1 2 3 4 5 6 7 8 9 a b c d e\n";
    for(r=0;r<15;++r) {
        cout.width(2);
        cout<<"0123456789abcde"[r];
        for(c=0;c<15;++c) {
            cout.width(2);
            char w=get(r, c);
            if(r==hl.row && c==hl.col) {
                if(w) {
                    cout<<"*"<<w;
                } else {
                    cout<<"*";
                }
            } else {
                if(w) {
                    cout<<w;
                } else {
                    cout<<'.';
                }
            }
        }
        cout<<endl;
    }
}
#endif

bool searchOpeningBook(Pos& p) {
    namespace b=board;
    if(b::obNotFound)
        return false;
    int i=b::obIndex, ob4me=b::iFirst?0:1, j;
    bool notFound=false;
    uint16_t const* ps=reinterpret_cast<uint16_t const*>(b::i8Steps);
    for(;i<obSize[ob4me];++i) {
        uint16_t const* pob=reinterpret_cast<uint16_t const*>(openingBook[ob4me][i]);
        notFound=false;
        for(j=0;j<b::ply;++j) {
            if( pob[j]!=ps[j] ) {
                notFound=true;
                break;
            }
        }
        if(notFound) {
            continue;
        } else {
            b::obIndex=i;
            p=Pos(openingBook[ob4me][i][j][0], openingBook[ob4me][i][j][1]);
            if(openingBook[ob4me][i][j+1][0]>=15) { // end
                b::obNotFound=true;
            }
            return true;
        }
    }
    b::obIndex=i;
    b::obNotFound=true;
    return false;
}

void flipH(int8_t (*to)[2], int8_t (*from)[2]) {
    int8_t (*t)[2]=to,(*f)[2]=from;
    for(;**f<15;++f,++t) {
        **t=**f;
        (*t)[1]=14-(*f)[1];
    }
    (*t)[0]=(*t)[1]=15;
}
void rotate90(int8_t (*to)[2], int8_t (*from)[2]) {
    int8_t (*t)[2]=to,(*f)[2]=from;
    for(;**f<15;++f,++t) {
        (*t)[0]=(*f)[1];
        (*t)[1]=14-(*f)[0];
    }
    (*t)[0]=(*t)[1]=15;
}

void initOpeningBook() {
    int i,j,k,l;
    for(i=0;i<2;++i) {
        for(j=0;j<obSize[i];++j) {
            // 1
            k=j;
            l=j+obSize[i];
            flipH(openingBook[i][l], openingBook[i][k]);

            // 2
            l+=obSize[i];
            rotate90(openingBook[i][l], openingBook[i][k]);

            // 3
            k=l;
            l+=obSize[i];
            flipH(openingBook[i][l], openingBook[i][k]);

            // 4
            l+=obSize[i];
            rotate90(openingBook[i][l], openingBook[i][k]);

            // 5
            k=l;
            l+=obSize[i];
            flipH(openingBook[i][l], openingBook[i][k]);

            // 6
            l+=obSize[i];
            rotate90(openingBook[i][l], openingBook[i][k]);

            // 7
            k=l;
            l+=obSize[i];
            flipH(openingBook[i][l], openingBook[i][k]);
        }
        obSize[i]*=8;
    }
}
class OpeningBookInitizer {
public:
    OpeningBookInitizer() {
        initOpeningBook();
    }
} openingBookInitizer;

inline void initBoard() {
    namespace b=board;
    memset(b::bX,0,sizeof(b::bX));
    memset(b::rbX,0,sizeof(b::rbX));
    memset(b::ltbX,0,sizeof(b::ltbX));
    memset(b::rtbX,0,sizeof(b::rtbX));

    memset(b::bO,0,sizeof(b::bO));
    memset(b::rbO,0,sizeof(b::rbO));
    memset(b::ltbO,0,sizeof(b::ltbO));
    memset(b::rtbO,0,sizeof(b::rtbX));

    memset(b::mark,0,sizeof(b::mark));
    memset(b::goodMoves,0,sizeof(b::goodMoves));
    memset(b::gmSize,0,sizeof(b::gmSize));
    memset(b::availableMoves,0,sizeof(b::availableMoves));
    memset(b::amSize,0,sizeof(b::amSize));
    memset(b::statistic,0,sizeof(b::statistic));

    memset(b::winLine,0,sizeof(b::winLine));
    memset(b::steps,0,sizeof(b::steps));

    memset(b::i8Steps,0,sizeof(b::i8Steps));
    b::obNotFound=false;
    b::obIndex=0;
    b::iFirst=0;

    b::hash=0;
    b::win=0;
    b::nThreats=0;
    b::ply=0;
    b::vfo=b::vfx=b::vto=b::vtx=0;

    b::startTime=0;
    b::endTime=0;

#ifdef DEBUG_GOMOKU
    b::nodesSearched=0; 
    b::tssNodeSearched=0;
#endif
}

inline void initEverything() {
    initBoard();
    memset(hashTable, 0, sizeof(HashKey)*HTCAPACITY);
}
// }}}
// {{{ core functions
// {{{ mark threats
// {{{ re-mark all
void markThreats() {
    namespace b=board;
    static const uint16_t s[]={0,1,2,4,8,16,32,64,128,-1,-1,-1};
    uint16_t *p16 =b::bO, 
             *xp16=b::bX;
    uint8_t   now=O;
    int       row,col;
    int       turn;
    int       playerIdx=0;
    b::win=0;
    memset(b::mark, 0, sizeof(b::mark));
    b::vto=b::vtx=b::vfo=b::vfx=0;
    for(turn=0; turn<2; ++turn, xp16=b::bO, p16=b::bX, now=X, playerIdx=1) {
        for(row=0;row<15;++row) {
            if (!p16[row]) continue;
            for(col=0;col<11;) {
                uint intr = (xp16[row]>>col)&31; // interrupted
                if(intr) {
                    ++col;
                    continue;
                }
                uint left,right;
                if (col>0) left =xp16[row]>>(col-1)&1;
                else       left =1;
                if (col<10)right=xp16[row]>>(col+5)&1;
                else       right=1;
                uint tmp = p16[row]>>col;
                uint16_t (*m)[5]=b::mark[playerIdx][row]+col;
                uint8_t const *S=maskTable[(left<<1)|right][tmp&31]+4;
                switch(tmp&31) {
                case 31:
                    b::win = now;
                    return;
                case 0:
                    col+=S[1];
                    continue;
                default:
                    m[0][1]|=s[*S--];
                    m[1][1]|=s[*S--];
                    m[2][1]|=s[*S--];
                    m[3][1]|=s[*S--];
                    m[4][1]|=s[*S--];
                }
                col+=S[6];
            }
        }
    }
    for(turn=0, p16=b::rbO, xp16=b::rbX, now=O, playerIdx=0; 
        turn<2; 
        ++turn, xp16=b::rbO, p16=b::rbX, now=X, playerIdx=1) {
        for(col=0;col<15;++col) {
            if (!p16[col]) continue;
            for(row=0;row<11;) {
                uint intr = (xp16[col]>>row)&31; // interrupted
                if(intr) {
                    ++row;
                    continue;
                }
                uint up,down;
                if (row>0) up=xp16[col]>>(row-1)&1;
                else       up=1;
                if(row<10) down=xp16[col]>>(row+5)&1;
                else       down=1;
                uint tmp = p16[col]>>row;
                uint8_t const *S=maskTable[(up<<1)|down][tmp&31]+4;
                uint16_t (*m)[16][5]=b::mark[playerIdx];
                switch(tmp&31) {
                case 31:
                    b::win = now;
                    return;
                case 0:
                    row+=S[1];
                    continue;
                default:
                    m[row  ][col][2]|=s[*S--];
                    m[row+1][col][2]|=s[*S--];
                    m[row+2][col][2]|=s[*S--];
                    m[row+3][col][2]|=s[*S--];
                    m[row+4][col][2]|=s[*S--];
                }
                row+=S[6];
            }
        }
    }
    for(turn=0, p16=b::ltbO, xp16=b::ltbX, now=O, playerIdx=0; 
        turn<2; 
        ++turn, p16=b::ltbX, xp16=b::ltbO, now=X, playerIdx=1) {
        int x,y;
        for(y=4;y<25;++y) {
            if(!p16[y]) continue;
            for(x=0;x<11;) {
                if((xp16[y]>>x)&31){ // interrupted
                    ++x;
                    continue;
                }
                row=affineLT[y][x];
                col=row&15;
                row>>=4;
                if(row<0||row>=11||col<0||col>=11) {
                    ++x;
                    continue;
                }
                uint left,right;
                if (row>0&&col>0) left =xp16[y]>>(x-1)&1;
                else     left =1;
                if (row<10&&col<10)right=xp16[y]>>(x+5)&1;
                else     right=1;
                uint tmp = p16[y]>>x;
                uint8_t const *S=maskTable[(left<<1)|right][tmp&31]+4;
                uint16_t (*m)[16][5]=b::mark[playerIdx];
                switch(tmp&31) {
                case 31:
                    b::win = now;
                    return;
                case 0:
                    x+=S[1];
                    continue;
                default:
                    m[row  ][col  ][3]|=s[*S--];
                    m[row+1][col+1][3]|=s[*S--];
                    m[row+2][col+2][3]|=s[*S--];
                    m[row+3][col+3][3]|=s[*S--];
                    m[row+4][col+4][3]|=s[*S--];
                }
                x+=S[6];
            }
        }
    }
    for(turn=0, p16=b::rtbO, xp16=b::rtbX, now=O, playerIdx=0; 
        turn<2; 
        ++turn, p16=b::rtbX, xp16=b::rtbO, now=X, playerIdx=1) {
        int x,y;
        for(y=4;y<25;++y) {
            if(!p16[y]) continue;
            for(x=0;x<11;) {
                if((xp16[y]>>x)&31){ // interrupted
                    ++x;
                    continue;
                }
                row=affineRT[y][x];
                col=row&15;
                row>>=4;
                if(row<0||row>=11||col<4||col>=15) {
                    ++x;
                    continue;
                }
                uint left,right;
                if (row<10&&col>4) left=xp16[y]>>(x+5)&1;
                else     left =1;
                if (row>0&&col<14)right=xp16[y]>>(x-1)&1;
                else     right=1;
                uint tmp = p16[y]>>x;
                uint8_t const *S=maskTable[(left)|(right<<1)][tmp&31]+4;
                uint16_t (*m)[16][5]=b::mark[playerIdx];
                switch(tmp&31) {
                case 31:
                    b::win = now;
                    return;
                case 0:
                    x+=S[1];
                    continue;
                default:
                    m[row  ][col  ][4]|=s[*S--];
                    m[row+1][col-1][4]|=s[*S--];
                    m[row+2][col-2][4]|=s[*S--];
                    m[row+3][col-3][4]|=s[*S--];
                    m[row+4][col-4][4]|=s[*S--];
                }
                x+=S[6];
            }
        }
    }
}
// }}} re-mark all
// {{{ update 4 lines
void updateLines(Pos p) {
    namespace b=board;
    static const uint16_t s[]={0,1,2,4,8,16,32,64,128,-1,-1,-1};
    uint16_t *p16 =b::bO, 
             *xp16=b::bX;
    uint8_t   now=O;
    int       row=p.row,col=p.col;
    int       turn;
    int       playerIdx=0;

    // init...
    b::win=0;
    b::vto=b::vtx=b::vfo=b::vfx=0;
    for(row=p.row, col=0; col<15; ++col) {
        b::mark[0][row][col][0] =
        b::mark[1][row][col][0] =
        b::mark[0][row][col][1] = 
        b::mark[1][row][col][1] = 0;
    }
    for(row=0, col=p.col; row<15; ++row) {
        b::mark[0][row][col][0] =
        b::mark[1][row][col][0] =
        b::mark[0][row][col][2] = 
        b::mark[1][row][col][2] = 0;
    }
    if(p.row>p.col) {
        row = p.row-p.col;
        col = 0;
        for(;row<15;++row, ++col) {
            b::mark[0][row][col][0] =
            b::mark[1][row][col][0] =
            b::mark[0][row][col][3] =
            b::mark[1][row][col][3] = 0;
        }
    } else {
        row = 0;
        col = p.col-p.row;
        for(;col<15;++row, ++col) {
            b::mark[0][row][col][0] =
            b::mark[1][row][col][0] =
            b::mark[0][row][col][3] =
            b::mark[1][row][col][3] = 0;
        }
    }
    row = p.row, col=p.col;
    if(row+col<14) {
        col+=row;
        row=0;
        for(;col>=0; --col, ++row) {
            b::mark[0][row][col][0] =
            b::mark[1][row][col][0] =
            b::mark[0][row][col][4] = 
            b::mark[1][row][col][4] = 0;
        }
    } else {
        row+=col;
        row-=14;
        col=14;
        for(;row<15; --col, ++row) {
            b::mark[0][row][col][0] =
            b::mark[1][row][col][0] =
            b::mark[0][row][col][4] = 
            b::mark[1][row][col][4] = 0;
        }
    }

    for(turn=0; turn<2; ++turn, xp16=b::bO, p16=b::bX, now=X, playerIdx=1) {
        row=p.row;
        if (!p16[row]) continue;
        for(col=0;col<11;) {
            uint intr = (xp16[row]>>col)&31; // interrupted
            if(intr) {
                ++col;
                continue;
            }
            uint left,right;
            if (col>0) left =xp16[row]>>(col-1)&1;
            else       left =1;
            if (col<10)right=xp16[row]>>(col+5)&1;
            else       right=1;
            uint tmp = p16[row]>>col;
            uint16_t (*m)[5]=b::mark[playerIdx][row]+col;
            uint8_t const *S=maskTable[(left<<1)|right][tmp&31]+4;
            switch(tmp&31) {
            case 31:
                b::win = now;
                return;
            case 0:
                col+=S[1];
                continue;
            default:
                m[0][1]|=s[*S--];
                m[1][1]|=s[*S--];
                m[2][1]|=s[*S--];
                m[3][1]|=s[*S--];
                m[4][1]|=s[*S--];
            }
            col+=S[6];
        }
    }
    for(turn=0, p16=b::rbO, xp16=b::rbX, now=O, playerIdx=0; 
        turn<2; 
        ++turn, xp16=b::rbO, p16=b::rbX, now=X, playerIdx=1) {
        col=p.col;
        if (!p16[col]) continue;
        for(row=0;row<11;) {
            uint intr = (xp16[col]>>row)&31; // interrupted
            if(intr) {
                ++row;
                continue;
            }
            uint up,down;
            if (row>0) up=xp16[col]>>(row-1)&1;
            else       up=1;
            if(row<10) down=xp16[col]>>(row+5)&1;
            else       down=1;
            uint tmp = p16[col]>>row;
            uint8_t const *S=maskTable[(up<<1)|down][tmp&31]+4;
            uint16_t (*m)[16][5]=b::mark[playerIdx];
            switch(tmp&31) {
            case 31:
                b::win = now;
                return;
            case 0:
                row+=S[1];
                continue;
            default:
                m[row  ][col][2]|=s[*S--];
                m[row+1][col][2]|=s[*S--];
                m[row+2][col][2]|=s[*S--];
                m[row+3][col][2]|=s[*S--];
                m[row+4][col][2]|=s[*S--];
            }
            row+=S[6];
        }
    }
    row=p.row, col=p.col;
    for(turn=0, p16=b::ltbO, xp16=b::ltbX, now=O, playerIdx=0; 
        turn<2; 
        ++turn, p16=b::ltbX, xp16=b::ltbO, now=X, playerIdx=1) {
        int x,y;
        y=row-col+14;
        if(y<4 || y>=25)
            continue;
        if(!p16[y]) continue;
        for(x=0;x<11;) {
            if((xp16[y]>>x)&31){ // interrupted
                ++x;
                continue;
            }
            row=affineLT[y][x];
            col=row&15;
            row>>=4;
            if(row<0||row>=11||col<0||col>=11) {
                ++x;
                continue;
            }
            uint left,right;
            if (row>0&&col>0) left =xp16[y]>>(x-1)&1;
            else     left =1;
            if (row<10&&col<10)right=xp16[y]>>(x+5)&1;
            else     right=1;
            uint tmp = p16[y]>>x;
            uint8_t const *S=maskTable[(left<<1)|right][tmp&31]+4;
            uint16_t (*m)[16][5]=b::mark[playerIdx];
            switch(tmp&31) {
            case 31:
                b::win = now;
                return;
            case 0:
                x+=S[1];
                continue;
            default:
                m[row  ][col  ][3]|=s[*S--];
                m[row+1][col+1][3]|=s[*S--];
                m[row+2][col+2][3]|=s[*S--];
                m[row+3][col+3][3]|=s[*S--];
                m[row+4][col+4][3]|=s[*S--];
            }
            x+=S[6];
        }
    }
    row=p.row, col=p.col;
    for(turn=0, p16=b::rtbO, xp16=b::rtbX, now=O, playerIdx=0; 
        turn<2; 
        ++turn, p16=b::rtbX, xp16=b::rtbO, now=X, playerIdx=1) {
        int x,y;
        y=row+col;
        if(y<4 || y>=25)
            continue;
        if(!p16[y]) continue;
        for(x=0;x<11;) {
            if((xp16[y]>>x)&31){ // interrupted
                ++x;
                continue;
            }
            row=affineRT[y][x];
            col=row&15;
            row>>=4;
            if(row<0||row>=11||col<4||col>=15) {
                ++x;
                continue;
            }
            uint left,right;
            if (row<10&&col>4) left=xp16[y]>>(x+5)&1;
            else     left =1;
            if (row>0&&col<14)right=xp16[y]>>(x-1)&1;
            else     right=1;
            uint tmp = p16[y]>>x;
            uint8_t const *S=maskTable[(left)|(right<<1)][tmp&31]+4;
            uint16_t (*m)[16][5]=b::mark[playerIdx];
            switch(tmp&31) {
            case 31:
                b::win = now;
                return;
            case 0:
                x+=S[1];
                continue;
            default:
                m[row  ][col  ][4]|=s[*S--];
                m[row+1][col-1][4]|=s[*S--];
                m[row+2][col-2][4]|=s[*S--];
                m[row+3][col-3][4]|=s[*S--];
                m[row+4][col-4][4]|=s[*S--];
            }
            x+=S[6];
        }
    }
}
// }}} update 4 lines
// }}}
// {{{ generate moves
// call me after markThreats
void genMoves(int depth, char who) {
    namespace b=board;
    int    r,c;
    uint16_t (*mark)[16][5]=b::mark[who==O?0:1];
    uint16_t (*markopp)[16][5]=b::mark[who==O?1:0];

    memset(b::gmSize[depth], 0, sizeof(b::gmSize[depth]));
    b::amSize[depth]=0;
    memset(b::statistic[0][depth], 0, sizeof(b::statistic[0][depth]));
    memset(b::statistic[1][depth], 0, sizeof(b::statistic[1][depth]));

    Threat *moves=b::availableMoves[depth];
    for(r=0;r<15;++r) {
        for(c=0;c<15;++c) {
            uint16_t *m=mark[r][c];
            m[0] = m[1]|m[2]|m[3]|m[4];
            Threat t={ Pos(r,c), m[0] };
            if(m[0] & 224) { // 6,7,8. ie. 4 or 5
                b::goodMoves[depth][3][b::gmSize[depth][3]++] = t;
            } else if(m[0] & 24) { // 4,5
                b::goodMoves[depth][2][b::gmSize[depth][2]++] = t;
            } 
#if 0 // ignore them
            else if(m[0] & 6) { // 2,3
                b::goodMoves[depth][1][b::gmSize[depth][1]++] = t;
            } else if(m[0]) { // 1
                b::goodMoves[depth][0][b::gmSize[depth][0]++] = t;
            }
#endif
            uint16_t *mopp=markopp[r][c];
            mopp[0] = mopp[1]|mopp[2]|mopp[3]|mopp[4];
            t.lvl = m[0];
            t.lvl<<=1;
            t.lvl+= mopp[0];
            if (t.lvl>0) {
                moves[b::amSize[depth]++] = t;
            }

            // statistic
            ++b::statistic[0][depth][highestBit[m[0]]];
            ++b::statistic[1][depth][highestBit[mopp[0]]];
        }
    }
    std::sort(moves, moves+b::amSize[depth]);
}
// }}}
// {{{ VCF finder
#if 1
// {{{ mark threat briefly - see threats in 8 lines only
// return: 
//  ( n directions ) <<4 | ( max threat level )
// arg threats:
//  threats[0] holds the size of array
//  threats[1 .. n] holds the pos of newly formed threats
uint8_t markThreatsBriefly(Pos p, char who, uint8_t* t4, uint8_t* t3) {
    namespace b=board;
    int      row=p.row,
             col=p.col,
             i,tmp,dx,dy;
    uint16_t o=b::bO[row],
             x=b::bX[row];
    uint16_t lv=0,c4=0,c3=0,
             idxO=(col>=4?o>>(col-4):o<<(4-col))&511,
             idxX=(col>=4?x>>(col-4):x<<(4-col))&511;
    uint32_t n,dir=0;

    // horizontal
    n=who==O?
        cachedThreats[idxO][idxX]:
        cachedThreats[idxX][idxO];
    if(n) {
        for(i=0;i<9;++i) {
            tmp=col-4+i;
            if((n>>i)&1 && tmp>=0 && tmp<15) {
                t4[++c4]=row<<4 | tmp;
            }
        }
        for(;i<18;++i) {
            tmp=col-4+i-9;
            if((n>>i)&1 && !((n>>(i-9))&1) && tmp>=0 && tmp<15) {
                t3[++c3]=row<<4 | tmp;
            }
        }
        ++dir;
        lv|=(n>>18)&7;
    }

    // vertical
    o=b::rbO[col];
    x=b::rbX[col];
    idxO=(row>=4?o>>(row-4):o<<(4-row))&511;
    idxX=(row>=4?x>>(row-4):x<<(4-row))&511;
    n=who==O?
        cachedThreats[idxO][idxX]:
        cachedThreats[idxX][idxO];
    if(n) {
        for(i=0;i<9;++i) {
            tmp = row-4+i;
            if((n>>i)&1 && tmp>=0 && tmp<15) {
                t4[++c4]=tmp<<4 | col;
            }
        }
        for(;i<18;++i) {
            tmp = row-4+i-9;
            if((n>>i)&1 && !((n>>(i-9))&1) && tmp>=0 && tmp<15) {
                t3[++c3]=tmp<<4 | col;
            }
        }
        ++dir;
        lv|=(n>>18)&7;
    }

    // \ diagnal
    dx=(row+col)>>1,dy=row-col+14;
    if(dy>=4 && dy<25) {
        o=b::ltbO[dy];
        x=b::ltbX[dy];
        idxO=(dx>=4?o>>(dx-4):o<<(4-dx))&511;
        idxX=(dx>=4?x>>(dx-4):x<<(4-dx))&511;
        n=who==O?
            cachedThreats[idxO][idxX]:
            cachedThreats[idxX][idxO];
        if(n) {
            for(i=0;i<9;++i) {
                tmp = dx-4+i;
                if((n>>i)&1 && affineLT[dy][tmp]!=255) {
                    t4[++c4]=affineLT[dy][tmp];
                }
            }
            for(;i<18;++i) {
                tmp = dx-4+i-9;
                if((n>>i)&1 && !((n>>(i-9))&1) && affineLT[dy][tmp]!=255) {
                    t3[++c3]=affineLT[dy][tmp];
                }
            }
            ++dir;
            lv|=(n>>18)&7;
        }
    }

    // / diagnal
    dx=(row-col+14)>>1,dy=row+col;
    if(dy>=4 && dy<25) {
        o=b::rtbO[dy];
        x=b::rtbX[dy];
        idxO=(dx>=4?o>>(dx-4):o<<(4-dx))&511;
        idxX=(dx>=4?x>>(dx-4):x<<(4-dx))&511;
        n=who==O?
            cachedThreats[idxO][idxX]:
            cachedThreats[idxX][idxO];
        if(n) {
            for(i=0;i<9;++i) {
                tmp = dx-4+i;
                if((n>>i)&1 && affineRT[dy][tmp]!=255) {
                    t4[++c4]=affineRT[dy][tmp];
                }
            }
            for(;i<18;++i) {
                tmp = dx-4+i-9;
                if((n>>i)&1 && !((n>>(i-9))&1) && affineRT[dy][tmp]!=255) {
                    t3[++c3]=affineRT[dy][tmp];
                }
            }
            ++dir;
            lv|=(n>>18)&7;
        }
    }

    t4[0]=c4;
    t3[0]=c3;
    return dir<<4|lv;
}
// }}}
// {{{ vcf
struct Threat4 {
    Pos attack;
    Pos defend;
};
class AutoSet {
    Pos p;
    char whoami;
    AutoSet(AutoSet const&);
    AutoSet& operator=(AutoSet const&);
public:
    AutoSet(Pos p, char whoami):
        p(p),
        whoami(whoami)
    {
        setLite(p, whoami);
    }
    ~AutoSet()
    {
        unsetLite(p, whoami);
    }
};

int tss(int nodeLimit, char whoami, uint8_t *t3, int  nt3, Pos* whereToGo=0);

// return: 0                 if no vcf exists
//         steps remained    if vcf exists
int hasVCF(char whoami, Threat4* threats, int len, int nodeLimit, Pos& whereToGo) {
    namespace b=board;
    if(nodeLimit<0) {
        dbg("hasVCF : reached limit\n");
        return 0;
    }
    dexec(++b::tssNodeSearched);
    uint8_t t4[16],t3[16],m;
    uint8_t ct4[16],ct3[16];
    char opp=X+O-whoami;
    int  res=0;
    bool chain=false;
    for(;;) {
        Threat4 t=*threats;
        ++threats;
        if(--len<0)
            break;
        if(get(t.attack) || get(t.defend))
            continue;
        for(int j=0;j<2;++j) {
            AutoSet att(t.attack, whoami);
            AutoSet def(t.defend, opp);
            chain=false;
            if(--nodeLimit<0) {
                return 0;
            }
            m=markThreatsBriefly(t.attack, whoami, t4, t3);
            if(m&4) {
                whereToGo=t.attack;
                return 1;
            }
            if(t4[0]>0) {
                if(markThreatsBriefly(t.defend, opp, ct4, ct3)&4) {
                    goto badLuck;
                } else {
                    whereToGo=t.attack;
                    return 3;
                }
            }
            if(t3[0]) {
                if(t3[0]!=2) {
                    uint8_t check=markThreatsBriefly(t.defend, opp, ct4, ct3);
                    int r;
                    if(check&4)
                        goto badLuck;
                    if(ct4[0] && !(markThreatsBriefly(Pos(ct4[1]), whoami, ct4, ct3)&6))
                        goto badLuck;
                    r=tss(nodeLimit,whoami,t3+1,t3[0]);
                    if(r>0) {
                        dbg("Yeah!\n");
                        whereToGo=t.attack;
                        return r+2;
                    }
                } else {
                    markThreatsBriefly(Pos(t3[1]), whoami, ct4, ct3);
                    if(ct4[0]>0 && (
                      (ct4[1]==t3[2]) || 
                      (ct4[0]>=2 && ct4[2]==t3[2]) || 
                      (ct4[0]>=3 && ct4[3]==t3[2]) )) {
                        --threats;
                        threats->attack=Pos(t3[1]);
                        threats->defend=Pos(t3[2]);
                        ++threats;
                        chain=true;
                    }
                }
            }
            if(chain)
                res=hasVCF(whoami, threats-1, len+1, nodeLimit, whereToGo);
            else
                res=hasVCF(whoami, threats,   len,   nodeLimit, whereToGo);
            if(res) {
                if(markThreatsBriefly(t.defend, opp, ct4, ct3)&4)
                    goto badLuck;
                if(ct4[0] && !(markThreatsBriefly(Pos(ct4[1]), whoami, ct4, ct3)&6))
                    goto badLuck;
                whereToGo=t.attack;
                return res+2;
            }
badLuck:
            std::swap(t.attack, t.defend);
        }
        *(threats-1)=t;
    }
    return 0;
}

int tss(int nodeLimit, char whoami, uint8_t* t3, int nt3, Pos* whereToGo) {
    Threat4 threats[128];
    uint8_t t4[16],t3_[16],m;
    int    threatCount=0;
    bool   alreadyIn;
    Pos    tmp;
    for(int i=0;i<nt3;++i) {
        Pos p(t3[i]);
        alreadyIn=false;
        for(int j=0;j<threatCount;++j) {
            if(p==threats[j].attack || p==threats[j].defend) {
                alreadyIn=true;
                break;
            }
        }
        if(alreadyIn)
            continue;
                
        AutoSet as(p, whoami);
        m=markThreatsBriefly(p, whoami, t4, t3_);
        if(t4[0]!=1) {
            if(t4[0]>1) {
                dbg("@_@ double-threat already exists!\n");
                if(whereToGo)
                    *whereToGo=p;
                return 3;
            }
        } else {
            threats[threatCount].attack=p;
            threats[threatCount].defend=Pos(t4[1]);
            ++threatCount;
        }
    }
    int res=hasVCF(whoami, threats, threatCount, nodeLimit, tmp);
    if(whereToGo!=0)
        *whereToGo=tmp;
    return res;
}
// }}}
#endif
// }}} VCF
// {{{ alpha-beta
// {{{ score
int score(uint16_t* mark, bool attacker) {
    static int const vTable[2][9] = { // 0 for me, 1 for opp
    //   1  2  3  4   5   6   7   8
        {0, 2, 7, 20, 80, 100,990,10000},
        {0, 1, 5, 16, 45, 98, 580,9000}
    };
    int res=0,t=0;
    int const *v=attacker?vTable[0]:vTable[1];
    int t3=0;

    if(mark[0]&96) { // has 4
        t3=t=0;
        if(mark[1]&96)++t;
        else if(mark[1]&24)++t3;
        if(mark[2]&96)++t;
        else if(mark[2]&24)++t3;
        if(mark[3]&96)++t;
        else if(mark[3]&24)++t3;
        if(mark[4]&96)++t;
        else if(mark[4]&24)++t3;
        if(t>1) { // double 4
            return attacker?10000:9000;
        } else if(t3) { // 4-3
            return attacker?9000:6000;
        }
    } else if(mark[0]&24) { // has open/broken - none blocked 3
        t=0;
        if(mark[1]&24)++t;
        if(mark[2]&24)++t;
        if(mark[3]&24)++t;
        if(mark[4]&24)++t;
        if(t>1) { // double 3
            return attacker?1000:800;
        }
    }

    res=v[highestBit[mark[1]]];
    t  =v[highestBit[mark[2]]];
    if(t&&res) {
        res+=t;
        res<<=1;
    } else {
        res+=t;
    }
    t  =v[highestBit[mark[3]]];
    if(t&&res) {
        res+=t;
        res<<=1;
    } else {
        res+=t;
    }
    t  =v[highestBit[mark[4]]];
    if(t&&res) {
        res+=t;
        res<<=1;
    } else {
        res+=t;
    }
    return res;
}
// }}}
// {{{ evaluate
int evaluate(int depth,char whoami) {
    using  board::mark;
    int    size=board::amSize[depth], me=whoami==O?0:1, opp, res=0;
    Threat *moves=board::availableMoves[depth];
    uint16_t *m;
    opp=1-me;

    for(int i=0;i<size;++i) {
        m=mark[me][moves[i].p.row][moves[i].p.col];
        res+=score(m, true);
        m=mark[opp][moves[i].p.row][moves[i].p.col];
        res-=score(m, false);
    }
    return res;
}
// }}} evaluate
int alphaBeta(int depth,int alpha,int beta,char whoami) {
    namespace b=board;
    dexec(++b::nodesSearched);
    HashKey const*key=htget(b::hash);
    int res=0;
    if(key&&key->depth>=depth) {
        res=key->v;
        if(res>WIN_VALUE) {
            res-=b::ply;
        } else if(res<-WIN_VALUE) {
            res+=b::ply;
        }
        switch(key->type) {
        case 0: // exact
            return res; 
            break;
        case 1: // alpha
            if(res<=alpha) return alpha;
            break;
        case 2: // beta
            if(res>=beta) return beta;
            break;
        }
    }
    res=0;
    int val,type=3;
    char opp=(whoami==O?X:O), foundPv=0;
    int const* statistic=b::statistic[0][depth],
             * oppStatistic=b::statistic[1][depth];

    // Null-Move Heuristic
    if (depth>=4&&b::steps[b::ply-1].row!=15) {
        b::steps[b::ply++]=Pos(15,15);
        b::hash^=0xfedcba9876543210ull;
        val=-alphaBeta(depth-3,-beta,std::min(-beta+1,-alpha),opp);
        b::hash^=0xfedcba9876543210ull;
        --b::ply;
        if(val>=beta) {
            return beta;
        }
    }
    // markThreats();
    if (b::win) {
        res=(whoami==b::win?MAX_VALUE:-MAX_VALUE);
        type=0;
        goto thatsit;
    } 
    genMoves(depth,whoami);
    type=0;
    if(statistic[7]) {           // has 4 already
        res=MAX_VALUE-1-b::ply;
        goto direct;
    } else if(statistic[6] &&    // can form a open 4 next move
             !oppStatistic[7]){  // cannnot defend
        res=MAX_VALUE-3-b::ply;
        goto direct;
    } else if(oppStatistic[5] && oppStatistic[7] ) {
        res=-MAX_VALUE+4+b::ply;
        goto direct;
    }

#if 1
    if(!oppStatistic[7]) {
        uint8_t *t3=b::tssStack[depth][0], nt3=0;
        Threat  *trt=b::goodMoves[depth][3];
        Pos     whereToGo;
        for(;nt3<b::gmSize[depth][3];++nt3) {
            t3[nt3]=trt[nt3].p.u8();
        }
        res=tss(64, whoami, t3, nt3, &whereToGo);
        if(res>0) {
#ifdef DEBUG_GOMOKU
            cout<<"Found TSS within "<<res<<" steps! (i am "<<whoami<<")\n";
            print(whereToGo);
            cout<<endl;
#endif
            res=-res-b::ply;
            res+=MAX_VALUE;
            goto direct;
        }
    }
#endif
    if (depth==0) {
        type=0;
        res=evaluate(0,whoami);
        goto thatsit;
    }
    for(int i=0,I=b::amSize[depth];i<I;++i) {
        if (clock()>b::endTime) {
            return beta+1;
        }

        Pos p(b::availableMoves[depth][i].p);
        set(p.row,p.col,whoami);
        updateLines(p);
        if(foundPv) {
            val=-alphaBeta(depth-1,-alpha-1,-alpha,opp);
            if((val>alpha)&&(val<beta)) {
                val=-alphaBeta(depth-1,-beta,-alpha,opp);
            }
        } else {
            val=-alphaBeta(depth-1,-beta,-alpha,opp);
        }
        unset(p.row,p.col,whoami);
        updateLines(p);

        if (val>=beta) {
            res=beta;
            type=2;
            goto thatsit;
        } else if (val>alpha) {
            alpha=val;
            foundPv=true;
        }
    }
    res=alpha;
    type=1;

thatsit:
    val=res;
    if(res>WIN_VALUE) {
        --val;
    } else if(res<-WIN_VALUE) {
        ++val;
    }
    htupdate(b::hash, type, depth, val);
    return val;

direct:
    val=res;
    if(res>WIN_VALUE) {
        val += b::ply;
    } else if(res<-WIN_VALUE) {
        val -= b::ply;
    }
    htupdate(b::hash, type, depth, val);
    
    return res;
}
// }}}
// {{{ make move
bool gt(std::pair<int,Pos>const&a,std::pair<int,Pos>const&b){
    return a.first>b.first;
}

Pos move() {
    namespace b=board;
    b::startTime=clock();
    b::endTime=b::startTime+timeLimit;
    std::pair<int,Pos> arr2[256];
    std::pair<int,Pos> *ia2=arr2,*eia2=arr2;
    int alpha=-MAX_VALUE,beta=MAX_VALUE,val;
    Pos bestMove(15,15),coor;
    int depth=1;
    if(searchOpeningBook(bestMove)) {
        dbg("Found in openingBook!\n");
        goto thatsit;
    }
    markThreats();
    genMoves(31,O);
#ifdef DEBUG_GOMOKU
    b::nodesSearched=0;
    b::tssNodeSearched=0;
#endif
    if (b::win) {
        return bestMove;
    }
    if(!b::statistic[1][31][7] && b::gmSize[31][3]) {
        uint8_t *t3=b::tssStack[31][0], nt3=0;
        Threat  *trt=b::goodMoves[31][3];
        for(;nt3<b::gmSize[31][3];++nt3) {
            t3[nt3]=trt[nt3].p.u8();
        }
        int res=tss(512, O, t3, nt3, &bestMove);
        if(res>0) {
#ifdef DEBUG_GOMOKU
            alpha=WIN_VALUE+1;
            dbg("Found TSS within %d steps!\n",res);
            print(bestMove);
            cout<<endl;
#endif
            goto thatsit;
        }
    }


    bestMove=Pos(b::availableMoves[31][0].p);
    for(depth=1;depth<16;++depth) {
        ia2=eia2=arr2;
        bool foundPv=false;
        for(int i=0,I=b::amSize[31];i<I;++i) {
            coor=b::availableMoves[31][i].p;
            set(coor.row,coor.col,O);
            updateLines(coor);
            if(foundPv) {
                val=-alphaBeta(depth-1,-alpha-1,-alpha,X);
                if(val>alpha&&val<beta) {
                    val=-alphaBeta(depth-1,-beta,-alpha,X);
                }
            } else {
                val=-alphaBeta(depth-1,-beta,-alpha,X);
            }
            unset(coor.row,coor.col,O);
            updateLines(coor);
            if (val>alpha) {
                alpha=val;
                bestMove=coor;
                foundPv=true;
            }
            *eia2++=std::make_pair(val,coor);
        }
        if(clock()>b::endTime) 
            break;
        std::sort(ia2,eia2,gt);
        for(b::amSize[31]=0;ia2!=eia2;++ia2) {
            if(ia2->first<=-WIN_VALUE)
                continue;
            b::availableMoves[31][b::amSize[31]++].p=ia2->second;
        }
        if(b::amSize[31]>10) {
            b::amSize[31]-=b::amSize[31]/6;
        }
    }

thatsit:
#ifdef DEBUG_GOMOKU
    if(alpha>WIN_VALUE)
        cout<<"I will win!"<<endl;
    else if(alpha<-WIN_VALUE)
        cout<<"Bad luck.."<<endl;
    cout<<"\n["<<(int)bestMove.col<<", "<<(int)bestMove.row<<"]\tAB: "<<b::nodesSearched<<" nodes; tss: "<<b::tssNodeSearched<<" nodes; max depth: "<<depth<<"; total time: "<<clock()-b::startTime<<"ms"<<endl;
#endif
    b::i8Steps[b::ply][0]=bestMove.row;
    b::i8Steps[b::ply][1]=bestMove.col;
    set(bestMove.row,bestMove.col,O);
    updateLines(bestMove);
    return bestMove;
}
// }}}
// }}} core functions
// {{{ PKU contest interface
void initAI() {
    char tmp[64];
    int  m,row,col;
    if(scanf("%d",&m)!=1)
        fprintf(stderr,"WTF\n");
    initEverything();
    if(scanf("%s%d%d",tmp,&col,&row)!=3)
        fprintf(stderr,"WTF\n");
    if(m == 2) {
        set(row, col, X);
        board::i8Steps[0][0]=row;
        board::i8Steps[0][1]=col;
        board::iFirst=false;
    } else if(m == 1) {
        board::iFirst=true;
    }
}

inline int random(int a, int b) {
    return a+rand()%(b-a+1);
}

void fightBack() {
    Pos p=move();
    printf("%d %d\n",p.col,p.row);
    fflush(stdout);
}

#ifndef USING_LINUX
int main() {
    char cmd[64];
    srand(time(0));
    while(scanf("%s",cmd)!=-1) {
        int row,col;
        if(!strcmp(cmd,"[START]")) {
            initAI();
            fightBack();
        } else if(!strcmp(cmd,"[PUT]")) {
            if(scanf("%d%d",&col,&row)!=2) {
                fprintf(stderr,"WTF\n");
            }
            board::i8Steps[board::ply][0]=row;
            board::i8Steps[board::ply][1]=col;
            set(row,col,X);
            fightBack();
        }
    }
    return 0;
}
#endif
// }}} interface

// vi:ts=4:et:sts=4:sw=4:foldmethod=marker:foldmarker={{{,}}}:foldlevel=0
